package com.wu.leetcode.sort.quicksort;

import java.util.Arrays;

/**
 * @author lynn
 * @date 2020/7/11 - 22:35
 * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {6, 3, 11, 6, 34, 7, 9, 5, 1, 6, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        //进行判断，如果左边的数值大于右边的 不合理直接退出
        if (left > right) {
            return;
        }
        //定义左边的索引
        int l = left;
        //定义右边的索引
        int r = right;
        //定义基准数  都以数组的左边为基准数
        int base = arr[left];
        //临时存放数值
        int temp = 0;
        //循环 当二者不相遇的时候一直检索
        //注意！！！左边的数为基准数的时候 从右边开始检索
        while (l != r) {
            //当右边的数大于或等于基准数的时候 继续检索 左移,且i不能大于j
            while (arr[r] >= base && l < r) {
                r--;
            }
            //当左边的数小于或等于基准数时 继续检索 右移 同样 l<r
            while (arr[l] <= base && l < r) {
                l++;
            }
            //当二者停下来的时候 可以交换数据
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //如果二者已将相遇  则将基准数和相遇的位置交换
        arr[left] = arr[l];
        arr[l] = base;

        //基准数归位是为了，左边的数字都比他小 右边的数字都比他大
        //排序左边
        quickSort(arr, left, l - 1);
        //排序右边
        quickSort(arr, l + 1, right);
    }
}
